import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

class Solution {
    public static void main(String[] args) {
        System.out.println(findSubstring("wordgoodgoodgoodbestword", new String[]{"word","good","best","good"}));
    }
    public static List<Integer> findSubstring(String s, String[] words) {
        List<Integer> list = new ArrayList<>() ;
        HashMap<String,Integer> map = new HashMap<>() ;
        HashMap<String,Integer> set = new HashMap<>() ;
        for(String str : words){
            if(map.containsKey(str) == false){
                map.put(str, 1);
            }else{
                map.put(str, map.get(str)+1);
            }
            set.put(str,0);
        }
        char[] nums = s.toCharArray() ;
        int numsLen = nums.length ;
        int wordLen = words[0].length() ;
        int wordSum = wordLen * words.length ;
        int len = words.length ;
        for(int i = 0 ; i < wordLen ; i ++){
            int count = 0 ;
            for(int left=i,right=i; right < numsLen-wordLen ; right += wordLen){
                String str = new String (nums, right , wordLen);
                if(set.containsKey(str)){
                    if(map.containsKey(str) == false){
                        set.put(str, set.get(str)+1);
                    }else if(set.get(str) < map.get(str)){
                        count ++ ;
                        set.put(str, set.get(str)+1);
                    }else{
                        set.put(str, set.get(str)+1);
                    }
                }else{
                    set.put(str,1);
                }
                if(right-left+1 > wordSum){
                    String str2 = new String(nums , left , wordLen);
                    if(map.containsKey(str2)){
                        if(set.get(str2) <= map.get(str2)){
                            count-- ;
                            set.put(str2, set.get(str2)-1);
                        }else{
                            set.put(str2, set.get(str2)-1);
                        }
                    }else{
                        set.put(str2, set.get(str2)-1);
                    }
                    left += wordLen ;
                }
                if(count == len){
                    list.add(left);
                }
            }
        }

        return list ;

    }
}